{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Unique Substrings in Wraparound String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSubstringInWraproundString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #环绕字符串中唯一的子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>定义字符串&nbsp;<code>base</code>&nbsp;为一个&nbsp;<code>\"abcdefghijklmnopqrstuvwxyz\"</code>&nbsp;无限环绕的字符串，所以&nbsp;<code>base</code>&nbsp;看起来是这样的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>\"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....\"</code>.</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>s</code> ，请你统计并返回&nbsp;<code>s</code>&nbsp;中有多少&nbsp;<strong>不同</strong><strong>非空子串</strong>&nbsp;也在&nbsp;<code>base</code>&nbsp;中出现。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>字符串 s 的子字符串 \"a\" 在 base 中出现。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"cac\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>字符串 s 有两个子字符串 (\"a\", \"c\") 在 base 中出现。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"zab\"\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>字符串 s 有六个子字符串 (\"z\", \"a\", \"b\", \"za\", \"ab\", and \"zab\") 在 base 中出现。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><font color=\"#c7254e\" face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size: 12.6px; background-color: rgb(249, 242, 244);\">s</span></font> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [unique-substrings-in-wraparound-string](https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [unique-substrings-in-wraparound-string](https://leetcode.cn/problems/unique-substrings-in-wraparound-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"a\"', '\"cac\"', '\"zab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = collections.defaultdict(int)\n",
    "        dp[s[0]] = 1\n",
    "        length = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if (ord(s[i]) - ord(s[i-1])) % 26 == 1:\n",
    "                length += 1\n",
    "            else:\n",
    "                length = 1\n",
    "            dp[s[i]] = max(dp[s[i]], length)\n",
    "\n",
    "        ans = 0\n",
    "        for ch, cnt in dp.items():\n",
    "            ans += cnt\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        l = 0\n",
    "        d = defaultdict(int)\n",
    "        for r, c in enumerate(s):\n",
    "            \n",
    "            if r == 0:\n",
    "                d[c] = 1\n",
    "                continue\n",
    "            \n",
    "            if (ord(c) - ord(s[r-1])) % 26 != 1:\n",
    "                l = r\n",
    "            d[c] = max(d[c], r - l + 1)\n",
    "          \n",
    "        return sum(d.values())\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        #记录字符i结尾的子串最长长度，也是子串的个数\n",
    "        dic=defaultdict(int)\n",
    "        #有就返回对应次数，没有就返回int\n",
    "        dic[s[0]]=1\n",
    "        res=1\n",
    "        for i in range(1,len(s)):\n",
    "            if (ord(s[i])-ord(s[i-1]))%26==1:\n",
    "                #%26兼容了1或-25\n",
    "                res+=1\n",
    "            else:\n",
    "                res=1\n",
    "            dic[s[i]]=max(dic[s[i]],res)\n",
    "        return sum(dic.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        dp=defaultdict(int)\n",
    "        k=0\n",
    "        for i ,ch in enumerate(s):\n",
    "            if i >0 and (ord(ch)-ord(s[i-1]))%26==1:\n",
    "                k+=1\n",
    "            else:\n",
    "                k=1\n",
    "            dp[ch]=max(dp[ch],k)\n",
    "        return sum(dp.values())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        l = 0\n",
    "        d = defaultdict(int)\n",
    "        for r, c in enumerate(s):\n",
    "            \n",
    "            if r == 0:\n",
    "                d[c] = 1\n",
    "                continue\n",
    "            \n",
    "            if (ord(c) - ord(s[r-1])) % 26 != 1:\n",
    "                l = r\n",
    "            d[c] = max(d[c], r - l + 1)\n",
    "          \n",
    "        return sum(d.values())\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        arr = [0 for _ in range(26)]\n",
    "        k = 0\n",
    "        for i in range(len(s)):\n",
    "            if k == 0:\n",
    "                k = 1\n",
    "            elif ord(s[i]) - ord(s[i - 1]) == 1 or s[i] == 'a' and s[i - 1] == 'z':\n",
    "                k += 1\n",
    "            else:\n",
    "                k = 1\n",
    "            arr[ord(s[i]) - 97] = max(arr[ord(s[i]) - 97], k)\n",
    "        return sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        dp = defaultdict(int)\n",
    "        k = 0\n",
    "        for i, ch in enumerate(p):\n",
    "            if i > 0 and (ord(ch) - ord(p[i - 1])) % 26 == 1:  # 字符之差为 1 或 -25\n",
    "                k += 1\n",
    "            else:\n",
    "                k = 1\n",
    "            dp[ch] = max(dp[ch], k)\n",
    "        return sum(dp.values())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2023/02/16 kc\n",
    "# key words: defaultdict (because unique), dp\n",
    "\n",
    "# 1. dic[char] = the longest length of substring ending with char\n",
    "# 2. traverse s, use dp[i], dp[i] : for each position i, consider s[i], the longest length end with that s[i] so far.\n",
    "# 3. put same char together to get the max in dic[char]\n",
    "\n",
    "# 官方题解： https://leetcode.cn/problems/unique-substrings-in-wraparound-string/solutions/1514359/huan-rao-zi-fu-chuan-zhong-wei-yi-de-zi-ndvea/\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        dic = defaultdict(int) # char: longest length end with this char\n",
    "        k = 1\n",
    "        for i, char in enumerate(s):\n",
    "            if i > 0 and (ord(s[i])-ord(s[i-1])) % 26 == 1:\n",
    "                k += 1\n",
    "            else:\n",
    "                k = 1\n",
    "            dic[char] = max(dic[char], k)\n",
    "        return sum(dic.values())\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        dic = defaultdict(int)    \n",
    "        k = 0           # this is dp[i] for saving space\n",
    "        for i, char in enumerate(s):\n",
    "            if i > 0 and (ord(char) - ord(s[i-1])) % 26 == 1:      # 字符之差为 1 或 -25\n",
    "                k += 1\n",
    "            else:\n",
    "                k = 1\n",
    "            dic[char] = max(dic[char], k)\n",
    "        return sum(dic.values())\n",
    "        # e.g. s = \"zab\"\n",
    "        #      dic = {\"z\": 1, \"a\": 2, \"b\": 3}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        dp = [0] * 26\n",
    "        n = len(s)\n",
    "        length = 1\n",
    "        for i in range(n - 1, -1 , -1):\n",
    "            c = ord(s[i]) - ord('a')\n",
    "            if length > 1:\n",
    "                dp[c] = max(dp[c], length - 1 )\n",
    "                length -= 1\n",
    "            else:\n",
    "                j = i\n",
    "                tmp = dp[c]\n",
    "                length = 1\n",
    "                while j - 1 >= 0:\n",
    "                    if s[j] == 'a' and s[j - 1] == 'z':\n",
    "                        length += 1\n",
    "                    elif ord(s[j]) - ord(s[j - 1]) == 1:\n",
    "                        length += 1\n",
    "                    else:\n",
    "                        break\n",
    "                    j -= 1\n",
    "                dp[c] = max(tmp, length)\n",
    "        return sum(dp)\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = defaultdict(lambda: 0)\n",
    "        prev = ord(s[0])-ord(\"a\")\n",
    "        tmp = 1\n",
    "        dp[prev] = 1\n",
    "        for i in range(n):\n",
    "            cur = ord(s[i])-ord(\"a\")\n",
    "            diff = (cur-prev) % 26\n",
    "            if diff == 1:\n",
    "                tmp += 1\n",
    "            else:\n",
    "                tmp = 1\n",
    "            dp[cur] = max(dp[cur], tmp)\n",
    "            prev = cur\n",
    "        # print(dp)\n",
    "        return sum(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        base='abcdefghijklmnopqrstuvwxyz'\n",
    "        d=[]\n",
    "        e=[]\n",
    "        t=''\n",
    "        for i in base:\n",
    "            d.append([i,0])\n",
    "        for a in s:\n",
    "            if t+a in base*(len(t+a)//26+2):\n",
    "                if len(t+a)>d[base.index((t+a)[0])][1]:\n",
    "                    d[base.index((t+a)[0])][1]=len(t+a)\n",
    "                    t+=a\n",
    "                else :t+=a\n",
    "            elif d[base.index(a[0])][1]==0:\n",
    "                d[base.index(a[0])][1]=1\n",
    "                t=a\n",
    "            else :t=a\n",
    "        for i in range(len(d)):\n",
    "            e.append(i+d[i][1])\n",
    "        for i in range(len(e)):\n",
    "            if e[i]<(max(e[:i]) if i>0 else 0) or e[i]<(max(e[i+1:]) if i<25 else 0)-26:\n",
    "                d[i][1]=0\n",
    "        e=[0]*26\n",
    "        for i in range(26):\n",
    "            for a in range(d[i][1]):\n",
    "                if d[i][1]-a>e[(i+a)%26]:\n",
    "                    e[(i+a)%26]=d[i][1]-a\n",
    "        return sum(e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 将字母序列转化为ASCAII码值，然后求相邻元素的差值\r\n",
    "# 最后如[1 0 3 1 1],则最后结果为 互异字母个数+(2+3)\r\n",
    "# class Solution:\r\n",
    "#     def findSubstringInWraproundString(self, s: str) -> int:\r\n",
    "#         ord_s = []\r\n",
    "#         count, res = 0, 0\r\n",
    "#         for c in s:\r\n",
    "#             ord_s.append(ord(c))\r\n",
    "#         print(ord_s)\r\n",
    "#         bias = len(set(ord_s))\r\n",
    "#         print(bias)\r\n",
    "#         for i in range(1, len(ord_s)):\r\n",
    "#             ord_s[i - 1] = ord_s[i] - ord_s[i - 1]\r\n",
    "#         ord_s.pop() #删除最后一个元素\r\n",
    "#         if ord_s == []:\r\n",
    "#             return 1\r\n",
    "#         if ord_s[0] in (1, -25):\r\n",
    "#             count += 1 \r\n",
    "#             res += count\r\n",
    "#         for i in range(1, len(ord_s)):  # 计算当前连续为1或-25的个数\r\n",
    "#             if ord_s[i] in (1, -25):\r\n",
    "#                 count += 1\r\n",
    "#             else:\r\n",
    "#                 count = 0\r\n",
    "#             res += count\r\n",
    "#         return res + bias\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\r\n",
    "        p = '^' + p\r\n",
    "        print(p)\r\n",
    "        len_mapper = collections.defaultdict(lambda: 0)\r\n",
    "        # w = 1\r\n",
    "        for i in range(1,len(p)):\r\n",
    "            if ord(p[i])-ord(p[i-1]) == 1 or ord(p[i])-ord(p[i-1]) == -25:\r\n",
    "                w += 1\r\n",
    "            else:\r\n",
    "                w = 1\r\n",
    "            len_mapper[p[i]] = max(len_mapper[p[i]], w)\r\n",
    "        return sum(len_mapper.values())\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        # 题目的意思 s 只是想表达 26 个英文字母字符串是环形的，即为 ...xyzabc...\n",
    "        # 然后要求输入一个 p 找出里面满足字母表环形的非空子串（且唯一）的数量\n",
    "\n",
    "        # dp 动态规划的思想，例如 abc 可以表示为：a b ab c bc abc\n",
    "        # a 结尾的子串数量(a) +  b 结尾的子串数量(b, ab) + c 结尾的子串数量(c, bc, abc)\n",
    "        # 假设 dp[i] 表示以第 i 个字符结尾的子串数量，那么状态转移方程为：\n",
    "        # 如果 i 和 i-1 字符在字母表是连续的：dp[i] = dp[i-1] + 1，前面基础上加多字符本身\n",
    "        # 如果 i 和 i-1 字符在字母表是不连续的：dp[i] = 1，只有字符本身能组成子串\n",
    "\n",
    "        from collections import defaultdict\n",
    "        index_to_sum = defaultdict(int)  # 用于存储 index -> 非空子串数量\n",
    "        char_to_sum = defaultdict(int)  # 用于存储 char -> 非空子串数量\n",
    "\n",
    "        for index, char in enumerate(p):\n",
    "            if index == 0:\n",
    "                # 第一个字符显然非空子串只能为 1，只能自己组成子串\n",
    "                index_to_sum[index] = 1\n",
    "                char_to_sum[char] = 1\n",
    "                continue\n",
    "            \n",
    "            # 第二个字符开始，我们判断相拼字符是否满足字母表顺序\n",
    "            # 通过判断当前字符和前一个字符，之差为 1 或 -25\n",
    "            if (ord(char) - ord(p[index - 1])) % 26 == 1:\n",
    "                # 满足字母表顺序，套用状态转移方程\n",
    "                index_to_sum[index] = index_to_sum[index - 1] + 1\n",
    "            else:\n",
    "                # 不满足字母表顺序，只能它本身构成一个子串\n",
    "                index_to_sum[index] = 1\n",
    "            \n",
    "            # 我们通过一个额外的字典对 char 进行映射，用来规避重复子串的统计\n",
    "            char_to_sum[char] = max(char_to_sum[char], index_to_sum[index])\n",
    "        \n",
    "        # 有了每个字符结尾的子串数量，进行求和得出最终结果\n",
    "        return sum(char_to_sum.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        if not p:\n",
    "            return 0\n",
    "        \n",
    "        n = len(p)\n",
    "        dp = [(0, 0)] * (n + 1)  # 状态为一个tuple，存储着以当前第i - 1个元素为底的最长连续子串长度，\n",
    "        occurence_dict = defaultdict(list)  # 存储以字母\"a\"结尾时的最长长度\n",
    "        dp[1] = (1, 1)\n",
    "        occurence_dict[p[0]] = 1\n",
    "\n",
    "        # TODO\n",
    "        # 转移方程为check当个是否出现，然后依次查询是否和前面的构成一个合法的子串\n",
    "        # 最差的复杂度是n^2\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            val = p[i -1]\n",
    "            pre_count, pre_continue_length = dp[i-1]\n",
    "            pre_val = p[i - 2]\n",
    "            # 如果没有出现过，则判断与之前是否连续\n",
    "            if not occurence_dict[val]:\n",
    "                if self.is_continuous(pre_val, val):\n",
    "                    dp[i] = (pre_count + pre_continue_length + 1, pre_continue_length + 1)\n",
    "                    occurence_dict[val] = pre_continue_length + 1\n",
    "                else:\n",
    "                    dp[i] = (pre_count + 1, 1)\n",
    "                    occurence_dict[val] = 1\n",
    "            else:\n",
    "                if self.is_continuous(pre_val, val):\n",
    "                    max_length = pre_continue_length + 1\n",
    "                    # 要查看当前为长度的最长纪录\n",
    "                    if occurence_dict[val] >= max_length:\n",
    "                        dp[i] = (pre_count, max_length)\n",
    "                    else:\n",
    "                        dp[i] = (pre_count + max_length - occurence_dict[val], max_length)\n",
    "                        occurence_dict[val] = max_length\n",
    "                else:\n",
    "                    dp[i] = (pre_count, 1)\n",
    "        return dp[-1][0]\n",
    "        \n",
    "    def is_continuous(self, s1, s2):\n",
    "        if (ord(s2) - ord(s1)) % 26 == 1:\n",
    "            return True\n",
    "        # if s1 == \"z\" and s2 == \"a\":\n",
    "        #    return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s1 = [0]*n \n",
    "        for i in range(n):\n",
    "            s1[i] = ord(s[i])-ord('a')\n",
    "        dp = [0]*26\n",
    "        dp[s1[0]] = 1\n",
    "        len1 = 1\n",
    "        for i in range(1,n):\n",
    "            cur = s1[i]\n",
    "            pre = s1[i-1]\n",
    "            if (pre==25 and cur==0) or (pre+1==cur):\n",
    "                len1+=1\n",
    "            else:\n",
    "                len1=1\n",
    "            dp[cur] = max(dp[cur],len1)\n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            ans += dp[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        nums = [0]*n\n",
    "        for i in range(n):\n",
    "            nums[i] = ord(s[i])-ord('a')\n",
    "        dp = [0]*26\n",
    "        dp[nums[0]] = 1\n",
    "        length = 1\n",
    "        for i in range(1,n):\n",
    "            \n",
    "            cur = nums[i]\n",
    "            pre = nums[i-1]\n",
    "            if pre+1==cur or (cur==0 and pre==25):\n",
    "                length += 1\n",
    "            else:\n",
    "                length = 1\n",
    "            dp[cur] = max(dp[cur],length)\n",
    "        return sum(dp)\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        \n",
    "        mp = {}\n",
    "\n",
    "        if not p:\n",
    "            return 0\n",
    "\n",
    "        for i in range(26):\n",
    "            mp[chr(ord('a')+i)] = i\n",
    "        \n",
    "        vis = {} ## 原本是存储字符串 p[i~j], 由于 不同的字符串开头只有26种， 可以降维成 26 * len(p),\n",
    "        # 即 ('a', 1) 表示 以 'a' 为开头，长度为1的字符串已经被访问了\n",
    "    \n",
    "\n",
    "        p_list = []\n",
    "\n",
    "        i = 0\n",
    "        n = len(p)\n",
    "        start = 0\n",
    "\n",
    "        \n",
    "        while i <= n:\n",
    "            if  i == n or i >0 and (mp[p[i-1]] + 1) % 26 != mp[p[i]]:\n",
    "                if (p[start], i - start ) not in vis:\n",
    "                    vis[(p[start], i - start )] = i - start \n",
    "\n",
    "                    ok = 1\n",
    "                    for x in p_list:\n",
    "                        if x.find(p[start:i]) >=0:\n",
    "                            ok = 0\n",
    "                            break\n",
    "                    if ok:\n",
    "                        p_list.append(p[start:i])\n",
    "                start = i\n",
    "\n",
    "            i +=1\n",
    "        \n",
    "        #print('p_list ', p_list)\n",
    "\n",
    "        vis.clear()\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for x in p_list:\n",
    "\n",
    "            cnt = 0\n",
    "            if (x[0], 1) not in vis:\n",
    "                vis[(x[0],1)] = 1\n",
    "                cnt +=1\n",
    "\n",
    "            for i in range(1, len(x)+1):\n",
    "                \n",
    "                #for j in range(i):\n",
    "\n",
    "                    #y = x[j:i]\n",
    "\n",
    "                if (x[i-1], len(x) - i+1  ) not in vis:\n",
    "                    vis[(x[i-1], len(x) - i + 1 )] = len(x) - i + 1\n",
    "                    cnt +=1\n",
    "            ans += cnt\n",
    "        \n",
    "\n",
    "        #print(vis)\n",
    "\n",
    "        mp2 = {}\n",
    "        for k, v in vis.items():\n",
    "            ch, v = k\n",
    "            if ch not in mp2 or mp2[ch] < v:\n",
    "                mp2[ch] = v\n",
    "\n",
    "        #print('mp2 ', mp2)       \n",
    "        ans = 0\n",
    "        for k, v in mp2.items():\n",
    "            ans += v\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        if not p:\n",
    "            return 0\n",
    "        \n",
    "        n = len(p)\n",
    "        dp = [(0, 0)] * (n + 1)  # 状态为一个tuple，存储着以当前第i - 1个元素为底的最长连续子串长度，\n",
    "        occurence_dict = defaultdict(list)  # 存储以字母\"a\"结尾时的最长长度\n",
    "        dp[1] = (1, 1)\n",
    "        occurence_dict[p[0]] = 1\n",
    "\n",
    "        # TODO\n",
    "        # 转移方程为check当个是否出现，然后依次查询是否和前面的构成一个合法的子串\n",
    "        # 最差的复杂度是n^2\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            val = p[i -1]\n",
    "            pre_count, pre_continue_length = dp[i-1]\n",
    "            pre_val = p[i - 2]\n",
    "            # 如果没有出现过，则判断与之前是否连续\n",
    "            if not occurence_dict[val]:\n",
    "                if self.is_continuous(pre_val, val):\n",
    "                    dp[i] = (pre_count + pre_continue_length + 1, pre_continue_length + 1)\n",
    "                    occurence_dict[val] = pre_continue_length + 1\n",
    "                else:\n",
    "                    dp[i] = (pre_count + 1, 1)\n",
    "                    occurence_dict[val] = 1\n",
    "            else:\n",
    "                if self.is_continuous(pre_val, val):\n",
    "                    max_length = pre_continue_length + 1\n",
    "                    # 要查看当前为长度的最长纪录\n",
    "                    if occurence_dict[val] >= max_length:\n",
    "                        dp[i] = (pre_count, max_length)\n",
    "                    else:\n",
    "                        dp[i] = (pre_count + max_length - occurence_dict[val], max_length)\n",
    "                        occurence_dict[val] = max_length\n",
    "                else:\n",
    "                    dp[i] = (pre_count, 1)\n",
    "        return dp[-1][0]\n",
    "        \n",
    "    def is_continuous(self, s1, s2):\n",
    "        if ord(s1) - ord(s2) == -1:\n",
    "            return True\n",
    "        if s1 == \"z\" and s2 == \"a\":\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findSubstringInWraproundString(self, p):\n",
    "\t\tj, a, c = 0, [ord(x) - ord('a') for x in p], [0] * 26\n",
    "\t\tfor i in range(len(a)):\n",
    "\t\t\tif i == 0 or a[i] != (a[i - 1] + 1) % 26: j = i\n",
    "\t\t\tc[a[i]] = max(c[a[i]], i - j + 1)\n",
    "\t\treturn sum(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        \"\"\"\n",
    "        连续子数组:前缀和+滑动窗口+pre\n",
    "\n",
    "        考虑p每个以i结尾得字符串总数\n",
    "        \"\"\"\n",
    "        n=len(p)\n",
    "        pre=p[0]\n",
    "        count=1\n",
    "        ans=set()\n",
    "        ans.add((pre,1))\n",
    "        for i in range(1,n):\n",
    "            if (ord(p[i])-ord(pre))%26==1:\n",
    "                count+=1\n",
    "            else:\n",
    "                count=1\n",
    "            \n",
    "            ans.add((p[i],count))\n",
    "            pre=p[i]\n",
    "        m=defaultdict(int)\n",
    "        for a,b in ans:\n",
    "            m[a]=max(m[a],b)\n",
    "        return sum([b for a,b in m.items()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        \n",
    "        # 这题用暴力思想会超时，难点在于如何去重。 注意到 字符串p的字符的种类有限(只有26种)，\n",
    "        # 利用有限的种类 来划分 不同的字符开头的字符串。\n",
    "        \n",
    "        ## 还需要发现 答案 = 以 不同种类开头/结尾的最长字符串长度之和 这一 规律。\n",
    "\n",
    "        mp = {}\n",
    "\n",
    "        if not p:\n",
    "            return 0\n",
    "\n",
    "        for i in range(26):\n",
    "            mp[chr(ord('a')+i)] = i\n",
    "        \n",
    "        vis = {} ## 原本是存储字符串 p[i~j], 由于 不同的字符串开头只有26种， 可以降维成 26 * len(p),\n",
    "        # 即 ('a', 1) 表示 以 'a' 为开头，长度为1的字符串已经被访问了\n",
    "    \n",
    "\n",
    "        p_list = []\n",
    "\n",
    "        i = 0\n",
    "        n = len(p)\n",
    "        start = 0\n",
    "\n",
    "        \n",
    "        while i <= n:\n",
    "            if  i == n or i >0 and (mp[p[i-1]] + 1) % 26 != mp[p[i]]:\n",
    "                if (p[start], i - start ) not in vis:\n",
    "                    vis[(p[start], i - start )] = i - start \n",
    "\n",
    "                    ok = 1\n",
    "                    for x in p_list:\n",
    "                        if x.find(p[start:i]) >=0:\n",
    "                            ok = 0\n",
    "                            break\n",
    "                    if ok:\n",
    "                        p_list.append(p[start:i])\n",
    "                start = i\n",
    "\n",
    "            i +=1\n",
    "        \n",
    "        #print('p_list ', p_list)\n",
    "\n",
    "        vis.clear()\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for x in p_list:\n",
    "\n",
    "            cnt = 0\n",
    "            if (x[0], 1) not in vis:\n",
    "                vis[(x[0],1)] = 1\n",
    "                cnt +=1\n",
    "\n",
    "            for i in range(1, len(x)+1):\n",
    "                \n",
    "                #for j in range(i):\n",
    "\n",
    "                    #y = x[j:i]\n",
    "\n",
    "                if (x[i-1], len(x) - i+1  ) not in vis:\n",
    "                    vis[(x[i-1], len(x) - i + 1 )] = len(x) - i + 1\n",
    "                    cnt +=1\n",
    "            ans += cnt\n",
    "        \n",
    "\n",
    "        #print(vis)\n",
    "\n",
    "        mp2 = {}\n",
    "        for k, v in vis.items():\n",
    "            ch, v = k\n",
    "            if ch not in mp2 or mp2[ch] < v:\n",
    "                mp2[ch] = v\n",
    "\n",
    "        #print('mp2 ', mp2)       \n",
    "        ans = 0\n",
    "        for k, v in mp2.items():\n",
    "            ans += v\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        last=[]\n",
    "        lastchar=\"A\"\n",
    "        ans=0\n",
    "        dp=[0]*26\n",
    "        for ch in s:\n",
    "            if ord(ch)==ord(lastchar)+1 or (ch==\"a\" and lastchar==\"z\"):\n",
    "                last.append(ch)\n",
    "            else:\n",
    "                #print(last)\n",
    "                #ans+=(1+last)*last//2\n",
    "                #print(ans)\n",
    "                l=len(last)\n",
    "                for i in range(l):\n",
    "                    o=ord(last[i])-ord(\"a\")\n",
    "                    dp[o]=max(dp[o],i+1)\n",
    "                last=[ch]\n",
    "            lastchar=ch\n",
    "        #print(last)\n",
    "        if last:\n",
    "            l=len(last)\n",
    "            for i in range(l):\n",
    "                o=ord(last[i])-ord(\"a\")\n",
    "                dp[o]=max(dp[o],i+1)\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "f(n)为字串个数\n",
    "f(1) = 1\n",
    "f(2) = 3 \n",
    "f(3) = 6 \n",
    "f(n) = (n+1)*n/2\n",
    "\n",
    "trick1，长度为k的，最多26种\n",
    "trick2，长度为k(k>=26)的 长度小于等于k-25的字串全部在都包含\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        start = 0\n",
    "        index = 1\n",
    "        res = set()\n",
    "        p += '#'\n",
    "        max_length = 0\n",
    "        while index < len(p):\n",
    "            if (ord(p[index])-ord(p[index-1])) in [1,-25]:\n",
    "                pass\n",
    "            else:\n",
    "                max_length = max(max_length, index-start)\n",
    "                res.add(p[start:index])\n",
    "                start = index\n",
    "            index += 1\n",
    "        count = 0\n",
    "        if max_length >= 26:\n",
    "            count += (max_length-25) * 26\n",
    "        # 接下来只需要处理长度大于max_length -25的\n",
    "        # 写一个函数，返回字符串k中，长度大于等于n的字串set\n",
    "        def set_s(k,n):\n",
    "            # 窗口的长度从n到k.length\n",
    "            kk = set()\n",
    "            for window_size in range(n, len(k)+1):\n",
    "                index = 0\n",
    "                while index < len(k) - window_size + 1:\n",
    "                    kk.add(k[index:index+window_size])\n",
    "                    index += 1\n",
    "            return kk\n",
    "        ws = max(max_length - 25 + 1, 1)\n",
    "        #print(ws)\n",
    "        res1 = set()\n",
    "        for x in res:\n",
    "            if len(x) >= ws:\n",
    "                res1.update(set_s(x, ws))\n",
    "        #print(res1)\n",
    "        return count + len(res1)\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        \n",
    "        mp = {}\n",
    "\n",
    "        if not p:\n",
    "            return 0\n",
    "\n",
    "        for i in range(26):\n",
    "            mp[chr(ord('a')+i)] = i\n",
    "        \n",
    "        vis = {}\n",
    "\n",
    "        p_list = []\n",
    "\n",
    "        i = 0\n",
    "        n = len(p)\n",
    "        start = 0\n",
    "\n",
    "        \n",
    "        while i <= n:\n",
    "            if  i == n or i >0 and (mp[p[i-1]] + 1) % 26 != mp[p[i]]:\n",
    "                if (p[start], i - start ) not in vis:\n",
    "                    vis[(p[start], i - start )] = i - start \n",
    "\n",
    "                    ok = 1\n",
    "                    for x in p_list:\n",
    "                        if x.find(p[start:i]) >=0:\n",
    "                            ok = 0\n",
    "                            break\n",
    "                    if ok:\n",
    "                        p_list.append(p[start:i])\n",
    "                start = i\n",
    "\n",
    "            i +=1\n",
    "        \n",
    "        print('p_list ', p_list)\n",
    "\n",
    "        vis.clear()\n",
    "\n",
    "        ans = 0\n",
    "        for x in p_list:\n",
    "\n",
    "            cnt = 0\n",
    "            if (x[0], 1) not in vis:\n",
    "                vis[(x[0],1)] = 1\n",
    "                cnt +=1\n",
    "\n",
    "            for i in range(1, len(x)+1):\n",
    "                \n",
    "                #for j in range(i):\n",
    "\n",
    "                    #y = x[j:i]\n",
    "\n",
    "                if (x[i-1], len(x) - i+1  ) not in vis:\n",
    "                    vis[(x[i-1], len(x) - i + 1 )] = len(x) - i + 1\n",
    "                    cnt +=1\n",
    "            ans += cnt\n",
    "        \n",
    "\n",
    "        print(vis)\n",
    "\n",
    "        mp2 = {}\n",
    "        for k, v in vis.items():\n",
    "            ch, v = k\n",
    "            if ch not in mp2 or mp2[ch] < v:\n",
    "                mp2[ch] = v\n",
    "\n",
    "        print('mp2 ', mp2)       \n",
    "        ans = 0\n",
    "        for k, v in mp2.items():\n",
    "            ans += v\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        n = len(p)\n",
    "        dp = [[0] * 27 for _ in range(n+1)]\n",
    "        def f(c):\n",
    "            return (ord(c) - ord('a'))%26\n",
    "        M = 0\n",
    "        def process(start, m):\n",
    "            for i in range(1, m+1):\n",
    "                j = 0\n",
    "                while i + j <= m and j < 26:\n",
    "                    dp[i][(start+j)%26] = 1\n",
    "                    j += 1\n",
    "\n",
    "        left = 0\n",
    "        for right in range(n):\n",
    "            if right < n-1 and (f(p[right]) + 1)%26 == f(p[right+1]):\n",
    "                continue\n",
    "            else:\n",
    "                # print(left, right)\n",
    "                M = max(M, right-left+1)\n",
    "                process(f(p[left]), right-left+1)\n",
    "                left = right + 1\n",
    "        ans = 0\n",
    "        for i in range(1, M+1):\n",
    "            ans += sum(dp[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, ch):\n",
    "        self.ch = ch\n",
    "        self.cnt = set()\n",
    "        self.cnt.add(0)\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        trie = Node(\"\")\n",
    "        t = trie\n",
    "\n",
    "        alpha = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        first = Node(\"a\")\n",
    "        t.next = first\n",
    "        t = t.next\n",
    "        index = dict()\n",
    "        index['a'] = first\n",
    "        for ch in alpha[1:]:\n",
    "            index[ch] = Node(ch)\n",
    "            t.next = index[ch]\n",
    "            t = t.next\n",
    "        \n",
    "        t.next = first\n",
    "\n",
    "        # p = trie\n",
    "        # for i in range(50):\n",
    "        #     print(p.ch)\n",
    "        #     p = p.next\n",
    "\n",
    "        last = p[0]\n",
    "        length = 1\n",
    "        index[last].cnt.add(length)\n",
    "        for now in p[1:]:\n",
    "            if index[last].next.ch!=now:\n",
    "                length = 1\n",
    "                index[now].cnt.add(length)\n",
    "            else:\n",
    "                length += 1\n",
    "                index[now].cnt.add(length)\n",
    "            last = now\n",
    "        \n",
    "        ans = 0\n",
    "        for ch in alpha:\n",
    "            ans += max(index[ch].cnt)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        s = [.5] + [ord(c) - ord('a') for c in s]\n",
    "        d = [0] * 26\n",
    "        start = cur = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if (s[i] - s[i - 1]) % 26 == 1:\n",
    "                cur += 1\n",
    "            else:\n",
    "                start, cur = s[i], 1\n",
    "            d[start] = max(d[start], cur)\n",
    "        for i in range(-25, 26):\n",
    "            d[i] = max(d[i], d[i - 1] - 1)\n",
    "        return sum(d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        s = [ord(c) - ord(\"a\") for c in s] + [255]\n",
    "        cnt = [0] * 26\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        for j in range(len(s)):\n",
    "            if i == j or s[j] - s[j - 1] == 1 or s[j] - s[j - 1] == -25:\n",
    "                continue\n",
    "            while i < j:\n",
    "                if j - i > cnt[s[i]]:\n",
    "                    ans += j - i - cnt[s[i]]\n",
    "                    cnt[s[i]] = j - i\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        def getsubstr(ss: str, t):\n",
    "            demo = t\n",
    "            if ss.index(t) == len(ss)-1:\n",
    "                return t\n",
    "            else:\n",
    "                for ii in range(ss.index(t) + 1, len(ss)):\n",
    "                    if ord(ss[ii])-ord(ss[ii - 1]) == 1 or ord(ss[ii])-ord(ss[ii - 1]) == -25:\n",
    "                        demo += ss[ii]\n",
    "                    if ord(ss[ii])-ord(ss[ii - 1]) != 1 and ord(ss[ii])-ord(ss[ii - 1]) != -25:\n",
    "                        if t in ss[(ss.index(t) + 1):(len(ss) + 1)]:\n",
    "                            return max(demo, getsubstr(ss[ss.index(t) + 1:len(ss) + 1], t))\n",
    "                        else:\n",
    "                            break\n",
    "            return demo\n",
    "        if len(p) == 1:\n",
    "            return 1\n",
    "        res = 0\n",
    "        ps = set()\n",
    "        for i in p:\n",
    "            ps.add(i)\n",
    "        pl = []\n",
    "        for i in ps:\n",
    "            pl.append(getsubstr(p, i))\n",
    "        for i in pl:\n",
    "            res += len(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # continuous_length[i] = max_{l} s.t. (s[j+1]-s[j])%26 == 1, for all i <= j < l-1\n",
    "        continuous_length = [0] * n\n",
    "        max_continous_length = defaultdict(int)\n",
    "        for i in reversed(range(n)):\n",
    "            if i < n-1 and (ord(s[i+1]) - ord(s[i]))%26 == 1:\n",
    "                continuous_length[i] = continuous_length[i+1] + 1\n",
    "            else:\n",
    "                continuous_length[i] = 1\n",
    "\n",
    "            # maximal valid substring starting with s[i]\n",
    "            max_continous_length[s[i]] = max(max_continous_length[s[i]], continuous_length[i])\n",
    "\n",
    "        ans = 0\n",
    "        for l in max_continous_length.values():\n",
    "            ans += l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        #base = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        n = len(s)\n",
    "        had = Counter()\n",
    "        had[s[0]] = 1\n",
    "        dp = [1] * n\n",
    "        for i in range(1, n):\n",
    "            pre = ord(s[i-1])\n",
    "            cur = ord(s[i])\n",
    "            if cur == pre + 1 or (s[i] == \"a\" and s[i-1] == \"z\"):\n",
    "                dp[i] = dp[i-1] + 1\n",
    "\n",
    "            if dp[i] > had[s[i]]:\n",
    "                had[s[i]] = dp[i] \n",
    "\n",
    "        ans = 0\n",
    "        for key in had:\n",
    "            ans += had[key]\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        def continuous(x, y):\n",
    "            if x == 'z':\n",
    "                return y == 'a'\n",
    "            return ord(y) - ord(x) == 1\n",
    "        \n",
    "        # dp[i]: 以 s[i] 结尾的子串个数\n",
    "        n = len(s)\n",
    "        dp = [1] * n\n",
    "        char2len = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            if i > 0 and continuous(s[i-1], s[i]):\n",
    "                dp[i] = dp[i-1] + 1 \n",
    "            char2len[s[i]] = max(char2len[s[i]], dp[i])\n",
    "        return sum(char2len.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        def isConsecutive(i, j):\n",
    "            idi = ord(i) - ord('a')\n",
    "            idj = ord(j) - ord('a')\n",
    "            return ((idj-idi)+26)%26 == 1\n",
    "        dp = [1] * len(p)\n",
    "        max_len = [0] * 26\n",
    "        max_len[ord(p[0])-ord('a')] = 1\n",
    "        for i in range(1, len(p)):\n",
    "            if isConsecutive(p[i-1], p[i]):\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            j = ord(p[i]) - ord('a')\n",
    "            max_len[j] = max(max_len[j], dp[i])\n",
    "        return sum(max_len)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "样例2,\n",
    "s = cac\n",
    "以 index 0 为结尾的子串有 c\n",
    "以 index 1 为结尾的子串有 a, ca(无效)\n",
    "以 index 2 为结尾的子串有 c, ac(无效), cac (无效) \n",
    "有重复, 所以是ans = 2\n",
    " \n",
    "s = zab\n",
    "以 index 0 为结尾的子串有 z = 1\n",
    "以 index 1 为结尾的子串有 a, za = 2 = 1 + f[0]\n",
    "以 index 2 为结尾的子串有 b, ab, zab = 1 + f[1] = 1 + 2 = 3\n",
    "\n",
    "s = abcdcd\n",
    "以 index 0 为结尾的子串有 a = 1\n",
    "以 index 1 为结尾的子串有 ab , b = 1 + 1 = 2\n",
    "以 index 2 为结尾的子串有 abc, bc, c, = 2 + 1 = 3\n",
    "以 index 3 为结尾的子串有 abcd, bcd, cd, d, 3 + 1 = 4 \n",
    "以 index 4 为结尾的子串有 c, 重复了\n",
    "以 index 5 为结尾的子串有 cd, d = 2, 重复了  \n",
    "'''\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        n = len(p)\n",
    "        mp = defaultdict(int)\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "\n",
    "        for i in range(n):\n",
    "            if i and ord(p[i]) - ord(p[i-1]) == 1 or ord(p[i]) - ord(p[i-1]) == -25:\n",
    "                f[i] = f[i-1] + 1\n",
    "            else:\n",
    "                f[i] = 1\n",
    "            \n",
    "            mp[p[i]] = max(mp[p[i]], f[i])\n",
    "        \n",
    "        return sum(mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        alp = collections.defaultdict(int)\n",
    "        dp = [1] * len(p)\n",
    "        for i in range(1, len(p)):\n",
    "            if p[i] == chr(ord(p[i-1]) + 1) or p[i] == chr(ord(p[i-1]) + 25) or chr(ord(p[i]) + 25) == p[i-1]:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "        for i in range(len(dp)):\n",
    "            alp[p[i]] = max(alp[p[i]], dp[i])\n",
    "        return sum(list(alp.values()))\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # continuous_length[i] = max_{l} s.t. (s[j+1]-s[j])%26 == 1, for all i <= j < l-1\n",
    "        continuous_length = [0] * n\n",
    "        max_continous_length = [0]*26\n",
    "        for i in reversed(range(n)):\n",
    "            if i < n-1 and (ord(s[i+1]) - ord(s[i]))%26 == 1:\n",
    "                continuous_length[i] = continuous_length[i+1] + 1\n",
    "            else:\n",
    "                continuous_length[i] = 1\n",
    "\n",
    "            # maximal valid substring starting with s[i]\n",
    "            max_continous_length[ord(s[i]) - ord('a')] = max(max_continous_length[ord(s[i]) - ord('a')], continuous_length[i])\n",
    "\n",
    "        return sum(max_continous_length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0]* n\n",
    "        char = [0] * 26\n",
    "\n",
    "        dp[0] = 1\n",
    "        char[ord(s[0])-ord('a')] = 1\n",
    "        for i in range(1,n):\n",
    "            if ord(s[i]) - ord(s[i-1]) == 1 or (s[i-1]=='z' and s[i] == 'a'):\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            else:\n",
    "                dp[i] = 1\n",
    "            \n",
    "            char[ord(s[i])-ord('a')] = max(\n",
    "                char[ord(s[i])-ord('a')],\n",
    "                dp[i]\n",
    "            )\n",
    "\n",
    "        return sum(char)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        p_len = len(p)\n",
    "        if p_len == 1:\n",
    "            return 1\n",
    "        dic = {}\n",
    "        cur_char = {}\n",
    "        s = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        for i in range(len(s)):\n",
    "            dic[s[i]] = i\n",
    "        dp = [0] * p_len\n",
    "        dp[0] = 1\n",
    "        cur_char[p[0]] = 1\n",
    "        for i in range(1, p_len):\n",
    "            if dic[p[i]] - dic[p[i - 1]] == 1:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "            elif p[i] == \"a\" and p[i - 1] == \"z\":\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "            else:\n",
    "                dp[i] = 1\n",
    "            if p[i] not in cur_char:\n",
    "                cur_char[p[i]] = dp[i]\n",
    "            else:\n",
    "                cur_char[p[i]] = max(cur_char[p[i]], dp[i])\n",
    "        res = 0\n",
    "        for k, v in cur_char.items():\n",
    "            res += v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [1 for i in range(n)]\n",
    "        max_l = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            if  i == 0:\n",
    "                max_l[s[0]] = 1\n",
    "                continue\n",
    "            if ord(s[i]) - ord(s[i-1]) == 1 or  ord(s[i]) - ord(s[i-1]) == -25:\n",
    "                dp[i]  = dp[i-1] + 1\n",
    "            max_l[s[i]] = max(max_l[s[i]],dp[i])\n",
    "\n",
    "        return sum(max_l.values())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#'''\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        dp = [1 for i in range(len(s))]\n",
    "        d = {s[0] : 1}\n",
    "        for i in range(1, len(s)):\n",
    "            if self.isnext(s[i], s[i-1]):  # 先后关系\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            else:\n",
    "                dp[i] = 1\n",
    "            d[s[i]] = max(dp[i], d.get(s[i], 0))\n",
    "        ans = 0\n",
    "        for k in d:\n",
    "            ans += d[k]\n",
    "        return ans\n",
    "    \n",
    "    def isnext(self, si, si_1):\n",
    "        return ord(si) == ord(si_1) + 1 or ord(si) == ord(si_1) - 25\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        dp = defaultdict(int)\n",
    "        k = 0\n",
    "        for i, ch in enumerate(p):\n",
    "            if i > 0 and (ord(ch) - ord(p[i - 1])) % 26 == 1:  # 字符之差为 1 或 -25\n",
    "                k += 1\n",
    "            else:\n",
    "                k = 1\n",
    "            dp[ch] = max(dp[ch], k)\n",
    "        print(dp)\n",
    "        return sum(dp.values())\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        dp = [1 for i in range(len(s))]\n",
    "        d = {s[0] : 1}\n",
    "        for i in range(1, len(s)):\n",
    "            if self.isnext(s[i], s[i-1]):  # 先后关系\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            else:\n",
    "                dp[i] = 1\n",
    "            d[s[i]] = max(dp[i], d.get(s[i], 0))\n",
    "        ans = 0\n",
    "        for k in d:\n",
    "            ans += d[k]\n",
    "        return ans\n",
    "    \n",
    "    def isnext(self, si, si_1):\n",
    "        return ord(si) == ord(si_1) + 1 or ord(si) == ord(si_1) - 25\n",
    "'''\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        dp = defaultdict(int)\n",
    "        k = 0\n",
    "        for i, ch in enumerate(p):\n",
    "            if i > 0 and (ord(ch) - ord(p[i - 1])) % 26 == 1:  # 字符之差为 1 或 -25\n",
    "                k += 1\n",
    "            else:\n",
    "                k = 1\n",
    "            dp[ch] = max(dp[ch], k)\n",
    "        print(dp)\n",
    "        return sum(dp.values())\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "\n",
    "    \n",
    "        pre_sum  = [1]*len(s)\n",
    "        find_word = [0]*26\n",
    "        find_word[ord(s[0])-ord(\"a\")]+=1\n",
    "\n",
    "        for i in range(1,len(s)):\n",
    "            if ord(s[i])-ord(s[i-1]) == 1 or ord(s[i])-ord(s[i-1]) == -25:\n",
    "                pre_sum[i] = pre_sum[i-1]+1\n",
    "            else :\n",
    "                pre_sum[i] = 1\n",
    "            find_word[ord(s[i])-ord(\"a\")] = max(find_word[ord(s[i])-ord(\"a\")],pre_sum[i]) \n",
    "\n",
    "        \n",
    "        return sum(find_word)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, p: str) -> int:\n",
    "        n = len(p)\n",
    "        dp = [1] * n\n",
    "        for i in range(1, n):\n",
    "            if ord(p[i]) - ord(p[i-1]) in [1, -25]:\n",
    "                dp[i] = 1 + dp[i-1]\n",
    "\n",
    "        rec = defaultdict(int)\n",
    "\n",
    "        for i in range(n):\n",
    "            rec[p[i]] = max(dp[i], rec[p[i]])\n",
    "\n",
    "        return sum(rec.values())\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [1]*n\n",
    "        count = [0]*26\n",
    "        index = ord(s[0]) - ord('a')\n",
    "        count[index] = 1 \n",
    "        # print(count)\n",
    "        for i in range(1,n):\n",
    "            if ord(s[i]) - ord(s[i-1]) == 1 or (s[i] == 'a' and s[i-1]=='z'):\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            char = s[i]\n",
    "            index = ord(char) - ord('a')\n",
    "            count[index] = max(count[index],dp[i])\n",
    "        # print(count)\n",
    "        # print(dp)\n",
    "\n",
    "        return sum(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "\n",
    "        dp=[1 for _ in range(n)]\n",
    "\n",
    "        cnt=collections.Counter()\n",
    "\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if  (ord(s[i-1])-ord(\"a\")+1)%26==(ord(s[i])-ord(\"a\")):\n",
    "                dp[i]=dp[i-1]+1\n",
    "            \n",
    "        for i in range(n):\n",
    "            a=s[i]   \n",
    "            if dp[i]>cnt[a]:\n",
    "                cnt[a]=dp[i]\n",
    "            \n",
    "\n",
    "                \n",
    "        #print(cnt)\n",
    "        return sum(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstringInWraproundString(self, s: str) -> int:\n",
    "        alpha = [0]*26\n",
    "        n = len(s)\n",
    "        alpha[ord(s[0])-ord('a')] = 1\n",
    "        dp = [1] *n \n",
    "\n",
    "        for i in range(1,n):\n",
    "            if s[i] == 'a' and s[i-1] == 'z':\n",
    "                dp[i] = dp[i-1]+1\n",
    "            if ord(s[i])-ord(s[i-1]) == 1:\n",
    "                dp[i] = dp[i-1]+1\n",
    "            \n",
    "\n",
    "            char = ord(s[i])-ord('a')\n",
    "\n",
    "            alpha[char] = max(alpha[char],dp[i])\n",
    "\n",
    "\n",
    "        return sum(alpha)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
